/*
*https://leetcode.cn/problems/find-k-closest-elements/
*658. 找到 K 个最接近的元素
* medium, 彭珵 2024.9.4
* 滑动窗口
*/

#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = 0; // 初始化左右指针
        int sum = 0; // 当前窗口的总和
        int minDiff = numeric_limits<int>::max(); // 最小差值初始化为最大值
        int a = 0, b = 0; // 用于记录最优窗口的左右边界

        // 遍历数组
        while (right < arr.size()) {
            // 计算当前元素与 x 的绝对差值并加入总和
            sum += abs(arr[right] - x);
            right++; // 移动右指针

            // 当窗口大小达到 k 时
            while (right - left == k) {
                // 更新最小差值和对应的左右边界
                if (sum < minDiff) {
                    a = left; // 更新左边界
                    b = right; // 更新右边界
                    minDiff = sum; // 更新最小差值
                }
                // 移出左边的元素，更新总和
                sum -= abs(arr[left] - x);
                left++; // 移动左指针
            }
        }

        // 构造结果
        vector<int> result(arr.begin() + a, arr.begin() + b);
        return result; // 返回结果
    }
};